\documentclass[E:/GsjzTle/main/main.tex]{subfiles}
\begin{document}

\begin{itemize}
\item
  \textbf{问题：}\\
  给出一个长度为 \(N\) 的正整数序列\\
  问是否存在一个长度不小于三的等差子序列（值域为 \(1e4\)）
\item
  \textbf{思路：}\\
  首先，找大于3个的和找3个的没区别。\\
  设置两个权值 \(bool\) 数组 \(pre,suf\)，假设当前时刻为 \(now\)

  若 \(pre_x=0\) 表示从 \(1\sim now\)，\(x\) 这个数并未出现过，反之表示
  \(x\) 这个数出现过，\\
  若\(suf_x=0\) 表示从 \(now\sim n\)，\(x\) 这个数并未出现过，反之表示
  \(x\) 这个数出现过\\
  那么此时以 \(a_{now}\) 为对称中心，以 \(n\) 或者 \(1\)
  为边界的对称区域\\
  若 \(pre_i = 1\) 并且 \(suf_j =1\) 并且 \(i\)、\(j\) 关于 \(a_{now}\)
  对称，则说明 \(2\times a_{now} = i+j\)

  -\/-\/-\/-\textgreater{} 问题转换成功
\item
  \textbf{解法 \(1\)：}\\
  直接上暴力，复杂度 \(O(n^2)\)
\item
  \textbf{解法 \(2\)：}\\
  用 \(bitset\) 优化暴力，复杂度 \(O(\dfrac{n^2}{32})\)
\item
  \textbf{解法 \(3\)：}\\
  可以用权值线段树+\(hash\) 来搞（序列必须为排列，思路和前面不一样了）\\
  设当前枚举的中点为 \(x\)，那么只要判断 \(x-len\sim x\) 和
  \(x \sim x+len\) 的 \(hash\) 值是否相同

  \begin{enumerate}
  \def\labelenumi{\arabic{enumi}.}
  \item
    若相同则说明可以和 \(x\) 构成等差的项都在前面出现过了。
  \item
    若不相同则说明有一组的一项在前面出现了，而另一项在前面没有出现过。因为序列是一个
    \(1\sim n\)的排列，所以另一项肯定在后面出现了。
  \end{enumerate}
\item
  \textbf{解法 \(4\)：}

  分块\(+ NTT\) （块的大小差不多为 \(2000\)）\\
  还可以求出有多少对 \(i,j,k\) 使得 \(a_i + a_k = 2\times a_j\)
\end{itemize}

\begin{lstlisting}
// bitset
#define rep(i , a , b) for(int i = a ; i <= b ; i ++)
using namespace std;
const int N = 2e4 + 10;
int a[N] , cnt[N];
bitset<N>pre , suf , x , y;
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0) , cout.tie(0);
	int T = 1;
	cin >> T;
	while(T --)
	{
		memset(cnt , 0 , sizeof(cnt));
		int n , flag = 0; 
		pre.reset() , suf.reset();
		cin >> n;
		rep(i , 1 , n) cin >> a[i] , suf.set(a[i]) , cnt[a[i]] ++ ;
		rep(i , 1 , n)
		{
			cnt[a[i]] -- ;
			if(!cnt[a[i]]) suf.reset(a[i]);
			int pre_add = a[i] - 1 , suf_add = 20000 - a[i]; 
			int add = min(pre_add , suf_add);
			x = pre >> (20001 - a[i] - add);
			y = suf >> (a[i] - add);
			if((x & y).count()) flag = 1 , i = n;
			pre.set(20000 - a[i] + 1); 
			// 个人习惯，我喜欢让 1 出现在最高位，2 出现在次高位。。。
		}
		if(flag) puts("Y");
		else puts("N");
	}
	return 0;
}
\end{lstlisting}

\begin{lstlisting}
// 权值线段树+hash
#define ull unsigned long long
const int P = 13331 , mod = 999998639; 
const int N = 2e5 + 10;
ull power[N];
int a[N];
struct Seg_ment{
	int l , r ;
	ull pre , suf;
}tree[N << 2];
void push_up(int id , int len1 , int len2)
{
	tree[id].pre = tree[id << 1].pre * power[len2] + tree[id << 1 | 1].pre;
	tree[id].pre %= mod;
	tree[id].suf = tree[id << 1 | 1].suf * power[len1] + tree[id << 1].suf;
	tree[id].suf %= mod;
}
void build(int id , int l , int r)
{
	tree[id].pre = tree[id].suf = 0; 
	tree[id].l = l , tree[id].r = r;
	if(l == r) return ;
	int mid = l + r >> 1;
	build(id << 1 , l , mid);
	build(id << 1 | 1 , mid + 1 , r);
	push_up(id , mid - tree[id].l + 1 , tree[id].r - mid);
}
void update(int id , int pos , int val)
{
	if(tree[id].l == tree[id].r)
	{
		tree[id].pre = tree[id].suf = val;
		return ;
	}
	int mid = tree[id].l + tree[id].r >> 1;
	if(pos <= mid) update(id << 1 , pos , val);
	else update(id << 1 | 1 , pos , val);
	push_up(id , mid - tree[id].l + 1 , tree[id].r - mid);
}
ull query_range(int id , int l , int r , int ch)
{
	if(tree[id].l >= l && tree[id].r <= r)
	{
		if(ch == 1) return tree[id].pre ;
		return tree[id].suf;
	}
	int mid = tree[id].l + tree[id].r >> 1;
	if(r <= mid) return query_range(id << 1 , l , r , ch);
	if(l > mid) return query_range(id << 1 | 1 , l , r , ch);
	ull lson = query_range(id << 1 , l , r , ch);
	ull rson = query_range(id << 1 | 1 , l , r , ch);
	ull ans ;
	if(ch == 1) ans = lson * power[min(r , tree[id].r) - mid] + rson;
	else ans = rson * power[mid - max(tree[id].l , l) + 1] + lson;
	return ans % mod;
}
void init()
{
	power[0] = 1;
	rep(i , 1 , 100000)
	power[i] = power[i - 1] * P % mod;
}
signed main()
{
	init();
	int t;
	cin >> t;
	while(t --)
	{
		int n , flag = 0 , x; 
		cin >> n;
		build(1 , 1 , n);
		rep(i , 1 , n)
		{
			cin >> x;
			update(1 , x , 1);
			if(i == 1 || i == n) continue ;
			int len = min(x , n - x + 1);
			int y = query_range(1 , x - len + 1 , x , 1);
			int z = query_range(1 , x , x + len - 1 , 2);
			if(y != z)	flag = 1 ;
		}
		if(flag) cout << "Y\n";
		else cout << "N\n";
	}
	return 0;
}
\end{lstlisting}

\begin{lstlisting}
//NTT+分块
#define int long long
#define M 100009
using namespace std;
int read()
{
	int f = 1, re = 0;
	char ch;
	for (ch = getchar(); !isdigit(ch) && ch != '-'; ch = getchar())
	;
	if (ch == '-')
	{
		f = -1, ch = getchar();
	}
	for (; isdigit(ch); ch = getchar())
	re = (re << 3) + (re << 1) + ch - '0';
	return re * f;
}
const int g = 3;
const int mod = 998244353;
int rev[M];
int ksm(int a, int b)
{
	int ans = 1;
	while (b)
	{
		if (b & 1) ans = (ll)ans * a % mod;
		a = (ll)a * a % mod;
		b >>= 1;
	}
	return ans % mod;
}
void ntt(int *A, int lim, int type)
{
	for (int i = 0; i < lim; i++) if (i < rev[i]) swap(A[i], A[rev[i]]);
	for (int mid = 1; mid < lim; mid <<= 1)
	{
		int W = ksm(g, (mod - 1) / (mid << 1));
		for (int R = mid << 1, j = 0; j < lim; j += R)
		{
			int w = 1;
			for (ll k = 0; k < mid; k++, w = (ll)w * W % mod)
			{
				int x = A[j + k], y = (ll)w * A[j + k + mid] % mod;
				A[j + k] = (x + y) % mod;
				A[j + mid + k] = (x - y + mod) % mod;
			}
		}
	}
	if (type == -1)
	{
		reverse(A + 1, A + lim);
		int inv = ksm(lim, mod - 2);
		for (int i = 0; i < lim; i++) A[i] = (ll)A[i] * inv % mod;
	}
}
int a[M], b[M], c[M], n, maxn, ans, num, L[M], R[M], l[M], r[M], block;
signed main()
{
	n = read();
	block = 2000;
	for (int i = 1; i <= n; i++) a[i] = read(), maxn = max(maxn, a[i]), r[a[i]]++;
	int lim = 1, lll = 0;
	while (lim < maxn * 2) lim <<= 1, lll++;
	for (int i = 0; i < lim; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (lll - 1));
	num = n / block;
	if (n % block) num++;
	for (int i = 1; i <= num; i++) L[i] = (i - 1) * block + 1, R[i] = i * block;
	R[num] = n;
	for (int i = 1; i <= num; i++)
	{
		for (int j = L[i]; j <= R[i]; j++) 		r[a[j]]--;
		for (int j = 0; j < lim; j++) 			b[j] = c[j] = 0;
		for (int j = 0; j <= maxn; j++) 		b[j] = l[j], c[j] = r[j];
		ntt(b, lim, 1), ntt(c, lim, 1);
		for (int j = 0; j < lim; j++) 			b[j] = (ll)b[j] * c[j];
		ntt(b, lim, -1);
		for (int j = L[i]; j <= R[i]; j++) 		ans += (ll)b[2 * a[j]];
		for (int j = L[i]; j <= R[i]; j++)
		{
			for (int k = L[i]; k < j; k++) if (2 * a[j] - a[k] > 0) ans += (ll)r[2 * a[j] - a[k]];
			for (int k = j + 1; k <= R[i]; k++) if (2 * a[j] - a[k] > 0) ans += (ll)l[2 * a[j] - a[k]];
			l[a[j]]++;
		}
	}
	printf("%lld\n", ans);
	return 0;
}
\end{lstlisting}

\end{document}
